package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://leetcode.cn/problems/count-complete-tree-nodes/description/
https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

示例 1：
输入：root = [1,2,3,4,5,6]
输出：6

示例 2：
输入：root = []
输出：0

示例 3：
输入：root = [1]
输出：1
 */
class leetcode_222 {
    @Test
    fun test_1() {
        val root: TreeNode = TreeNode(1)
        val n2: TreeNode = TreeNode(2)
        val n3: TreeNode = TreeNode(3)
        val n4: TreeNode = TreeNode(4)
        val n5: TreeNode = TreeNode(5)
        val n6: TreeNode = TreeNode(6)
        root.left = n2
        root.right = n3
        n2.left = n4
        n2.right = n5
        n3.left = n6

        val actual = countNodes(root)
        val expect = 6
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val actual = countNodes(null)
        val expect = 0
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_3() {
        val root: TreeNode = TreeNode(1)
        val actual = countNodes(root)
        val expect = 1
        Assert.assertEquals(expect, actual)
    }

    private fun countNodes(root: TreeNode?): Int {
        return countNodes4(root)
    }

    private fun countNodes1(root: TreeNode?): Int {
        // 普通二叉树： 深度遍历 - 后序 - 递归
        // T - N
        // S - N
        if(null ==  root){
            return 0
        }
        // 左
        val leftCount:Int = countNodes1(root.left)
        // 右
        val rightCount:Int = countNodes1(root.right)
        // 中
        val count:Int  = 1 +leftCount + rightCount
        return count
    }

    private fun countNodes2(root: TreeNode?) :Int{
        // 普通二叉树： 深度遍历 - 前序 - 递归
        // T - N
        // S - N
        if(null ==  root){
            return 0
        }
        var count:Int = 0
        // 中
        count ++
        // 左
        count = count + countNodes2(root.left)
        // 右
        count = count + countNodes2(root.right)
        return count
    }

    private fun countNodes3(root: TreeNode?) :Int{
        // 普通二叉树： 深度遍历 - 中序 - 递归
        // T - N
        // S - N
        if(null ==  root){
            return 0
        }
        var count = 0
        // 左
        count = count + countNodes3(root.left)

        // 中
        count++

        // 右
        count = count + countNodes3(root.right)
        return count
    }


    private fun countNodes4(root: TreeNode?): Int {
        // 完全二叉树： 深度遍历 - 后序 - 递归
        // 终止条件
        if (root == null) {
            return 0
        }
        var leftDepth: Int = 0
        var left: TreeNode? = root.left
        while (left != null) {
            leftDepth++
            left = left.left
        }
        var rightDepth: Int = 0
        var right: TreeNode? = root.right
        while (right != null) {
            rightDepth++
            right = right.right
        }

        // 满二叉树
        if (leftDepth == rightDepth) {
            // 左移操作符
            // 2的k 次方-1
            // todo : 注意 左移 shl，和优先级顺序
            return (2 shl leftDepth) - 1
        }

        // 左
        val leftNum: Int = countNodes4(root.left)

        // 右
        val rightNum: Int = countNodes4(root.right)

        // 中
        val num: Int = 1 + leftNum + rightNum
        return num
    }

    private fun countNodes5(root: TreeNode?) :Int{
        // 普通二叉树 - 广度遍历
        // S - N
        // T - N
        if(null == root){
            return 0
        }
        var count:Int = 0
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while(!queue.isEmpty()){
            var size = queue.size
            while(size-- > 0){
                count++
                val node : TreeNode = queue.poll()
                node.left?.let{queue.offer(it)}
                node.right?.let{queue.offer(it)}
            }
        }
        return count
    }
}